import java.io.File;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * This is an implementation of a maze solver.  First, the starting and
 * ending rooms are stored.  Then, the set of room adjacencies are stored
 * in a map structure where the rooms (keys) are associated with an implicit
 * linked lists of the rooms that may be reached in one step.
 */

public class MazeSolver
{
	
	// The set of directed connections between rooms
	private MyMap<Room, Node<Room>> cnxs;
	// The starting and ending rooms of the maze
	private Room start, end;
	
	/**
	 * Create an empty maze
	 */
	public MazeSolver()
	{
		// TODO: Implement!
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * Create a new maze which is initialized according to the data in the
	 *   given file
	 * @param path the maze file to read
	 */
	public MazeSolver(String path)
	{
		// TODO: Implement!
		//throw new RuntimeException("You must implement this method!");
		cnxs = new MyLLMap<Room, Node<Room>>();
		this.importMaze(path);
		Node<Room> tmp = this.solve();
		if (this.isValidPath(tmp)){
			System.out.println(tmp);
		}
		else{
			System.out.println("can not solve the maze");
		}
	}
	
	/**
	 * addConnection -- create a directed connection between the given
	 *   rooms
	 * @param fromRoom the source room
	 * @param toRoom the destination room
	 */
	public void addConnection(Room fromRoom, Room toRoom)
	{
		// if the key is valid
		if (!cnxs.contains(fromRoom)){
			//throw new RuntimeException("the fromRoom is not contained in the map");
			Node<Room> tmp = new Node<Room>(toRoom,cnxs.get(fromRoom));
			cnxs.put(fromRoom, tmp);
			return;
		}
		
		// Add this room in the front of the connected room list:
		Node<Room> tmp = new Node<Room>(toRoom,cnxs.get(fromRoom));
		// since we cannot set the value of the map, we have to delete previous pairs
		// then add a new one
		cnxs.remove(fromRoom);
		cnxs.put(fromRoom, tmp);
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * isConnected -- determine whether there is a directed connection
	 *   between the given rooms
	 * @param fromRoom the source room
	 * @param toRoom the destination room
	 * @return true if a connection exists, false otherwise
	 */
	public boolean isConnected(Room fromRoom, Room toRoom)
	{
		// check the status of the map 
		if (!cnxs.contains(fromRoom)){
			return false;
		}
		
		// Traverse the connected list to find out specific toRoom
		Node<Room> tmp = cnxs.get(fromRoom);
		while(tmp != null){
			if (tmp.getData().equals(toRoom)){
				return true;
			}
			tmp = tmp.getNext();
		}
		
		// did not find specific room
		return false;
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * importMaze -- initialize the maze with the data in the given file
	 * @param path the maze file
	 * @return true if the import was successful, false otherwise
	 */
	public boolean importMaze(String path)
	{
		try
		{
			Scanner input = new Scanner(new File(path));
			String line = input.nextLine();
			
			// Direct file format
			if (line.equals("D"))
				importMazeDirect(input);
			// List file format
			else if (line.equals("L"))
				importMazeList(input);
			// Unknown format; error
			else
				throw new RuntimeException("Unknown format");
			
			return true;
		}
		catch (Exception e)
		{
			System.out.println(e);
			return false;
		}
	}
	
	/** Helper function to import "direct" format */
	private void importMazeDirect(Scanner input)
	{
		int rows, cols, r, c;
		Room room, roomOther;
		String line;
		
		// Read the number of rows a columns, assume 2D
		rows = input.nextInt();
		cols = input.nextInt();
		input.nextLine();
		
		// Iterate over the rows
		for (r = 0; r < rows; r++)
		{
			line = input.nextLine();
			// Iterate over the columns
			for (c = 0; c < cols; c++)
			{
				// Quit if the room is a wall
				char ch = line.charAt(c);
				if (ch == 'X')
					continue;
				
				// Add the room to the data
				room = new Room(new int[]{r, c});
				cnxs.put(room, null);
				
				// Determine if it is a starting/ending room
				if (ch == '+')
					start = room;
				else if (ch == '-')
					end = room;
				
				// Add the open adjacent rooms to the connections
				Node<Room> adj = room.getNeighbors();
				while (adj != null)
				{
					roomOther = adj.getData();
					if (cnxs.contains(roomOther))
					{
						addConnection(room, roomOther);
						addConnection(roomOther, room);
					}
					adj = adj.getNext();
				}
			}
		}
		
	}
	
	/** Helper function to import "list" format */
	private void importMazeList(Scanner input)
	{
		StringTokenizer t;
		int[] coord, coord2;
		int k;
		
		// Get the number of dimensions
		int dim = Integer.parseInt(input.nextLine());
		
		// Iterate through the lines of the file
		while (input.hasNextLine())
		{
			// Break apart the lines into coordinates
			t = new StringTokenizer(input.nextLine(), "(), ");
			
			// Parse the first room
			coord = new int[dim];
			for (k = 0; k < dim; k++)
				coord[k] = Integer.parseInt(t.nextToken());
			
			// Initialize the start room
			if (start == null)
				start = new Room(coord);
			// Initialize the end room
			else if (end == null)
				end = new Room(coord);
			// Read the next room and create a connection
			else
			{
				coord2 = new int[dim];
				for (k = 0; k < dim; k++)
					coord2[k] = Integer.parseInt(t.nextToken());
				addConnection(new Room(coord), new Room(coord2));
			}
		}
	}
	
	/**
	 * isValidPath -- determine whether the given path represents a
	 *   valid walk through the maze
	 * @param path the first node in a linked list containing the
	 *   rooms in the path
	 * @return true if the path was valid, false otherwise
	 */
	public boolean isValidPath(Node<Room> path)
	{
		// check the whether the node is null before use it
		if (path == null){
			return false;
		}
		// check whether first room is start point
		if (!path.getData().equals(start)){
			return false;
		}
		
		Node<Room> pre = path;
		Node<Room> next = path.getNext();
		
		// make sure every step is valid
		while (next != null){
			//check a move is valid
			if (!this.isConnected(pre.getData(), next.getData())){
				return false;
			}
			
			// update the pointer
			pre = next;
			next = next.getNext();
		}
		
		// check whether the last room is end
		if (pre.getData().equals(end)){
			return true;
		}
		else{
			return false;
		}
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * solve -- Solve the given maze by finding a path from the start
	 *   room to the end room
	 * @return the first node in a linked list containing the rooms in
	 *   the path, and null if no path could be found
	 */
	public Node<Room> solve()
	{
		MyLLStack<Room> stack = new MyLLStack<Room>();
		if (!solveHelper(start, stack)){
			return null;
		}
		else{
			Node<Room> tmp = null;
			while (!stack.isEmpty()){
				Room room = stack.pop();
				Node<Room> node = new Node<Room>(room,tmp);
				tmp = node;
			}
			return tmp;
		}
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * solveHelper -- solve the maze working from the given room and
	 *   having already visited the rooms stored in the given stack
	 * @param room the current room
	 * @param stack the stack of visited rooms
	 * @return true if a path has been found which includes the current
	 *   room (leave visited rooms on stack), false otherwise (remove
	 *   room from stack) 
	 */
	private boolean solveHelper(Room room, MyStack<Room> stack)
	{
		// save the last room
		Room preRoom = stack.pop();
		// should not push the null into stack, this is only happen when first call solveHelper
		if (preRoom != null){
			stack.push(preRoom);
		}	
		// record this room
		stack.push(room);
		
		// Basic Case:
		if (room.equals(end)){
			return true;
		}
		
		// Recursive Case:
		Node<Room> conRoom;
		conRoom = cnxs.get(room);
		while(conRoom != null){
			// we can not go back,meaning if the next available room is last room, 
			// we just skip this room
			if (conRoom.getData().equals(preRoom)){
				conRoom = conRoom.getNext();
				continue;
			}
			
			// if not the last room we try to make a step
			if (solveHelper(conRoom.getData(),stack)){
				return true;
			}
			else{
				conRoom = conRoom.getNext();
			}
		}
		
		// go through all the connected room but did not find a end room
		// first pop this room
		stack.pop();
		return false;
		//throw new RuntimeException("You must implement this method!");
	}
	
}
